A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
The packets are transmitted between the source device and destination device using intermediate network devices, such as gateways, firewalls, switches and routers. When a network receives an incoming packet or sends an outgoing packet, the network device may apply one or more filters to the packet to perform a defined action on the packet under certain conditions. In order to identify the terms of the filters to apply to a given packet, the network device may extract information from the packet, such as a source or destination Internet Protocol (IP) address, a source or destination port, and protocol. The network device then performs a search of the filter terms installed within the network device to determine whether the extracted information satisfies criteria specified by any of the filter terms.
One conventional approach to identifying matching filter terms to apply to packets includes applying a hash function to at least a portion of the extracted information (i.e., a key) to determine possible locations in a hash table for the extracted information. A key corresponds to a portion of the extracted information having a predefined length (e.g., a prefix of a source or destination IP address). That is, one or more keys are inputted into a hash function to generate one or more possible locations in a hash table. The network device then looks up each possible location in the hash table to determine if the key is found in any of the possible locations. A key is found in the hash table when one or more filter terms are defined for the possible location. According to a longest prefix match algorithm, the router applies the filter terms associated with the longest prefix for which a match is found for the corresponding key in the hash table.
In order to improve the speed at which the network device identifies filter terms to apply to the packets, the network device may be configured to concurrently evaluate multiple different prefix lengths of a particular network address for possible matches with address prefixes in the hash table. However, the number of different prefixes generated from the different prefix lengths that may be evaluated concurrently may be limited by various hardware or software constraints.